package sun.scheduler.util.graph;

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;

/**
 * Represents an Iterarator that iterates over all Nodes inside of a 
 * {@link Graph} in breadth first seachr traversion order. 
 * The Traversion can be performed in two different modes: first by traversion 
 * trough all nodes that are reachable by a certain start node and second over 
 * all nodes in the specified graph.
 *
 * @param <N> the generic type of the {@link Node} data.
 * @param <E> the generic type of the {@link Edge} data.
 * @see Graph
 * @see Node
 * @see Edge
 * @author mfj
 */
public class BFSIterator<N, E> implements Iterator<Node<N, E>>
{
    private static final int UNVISITED = -2;

    private static final int NO_PREDESSOR = -1;

    private int nodeCount;

    private int expectedEdgeModCound;

    private int minInitID;

    private LinkedList<Node<N, E>> queue = new LinkedList<Node<N, E>>();

    private int[] predTable;

    protected Graph<N, E> graph;


    /**
     * Instantiates a new {@link BFSIterator} that traverses over all nodes 
     * that are reacheable from the specified start node.
     * @param start the node from which to start the traversion.
     */
    public BFSIterator(Node<N, E> start)
    {
        this.graph = start.graph;
        this.nodeCount = graph.getNumOfNodes();
        this.expectedEdgeModCound = graph.getEdgeModCount();
        this.minInitID = nodeCount;
        this.predTable = new int[nodeCount];

        queue.add(start);
        Arrays.fill(predTable, UNVISITED);
        predTable[start.id] = NO_PREDESSOR;
    }


    /**
     * Gets a new {@link BFSIterator} that iterates over all nodes of the specified graph.
     * @param graph the graph over which to iterate.
     */
    public BFSIterator(Graph<N, E> graph)
    {
        this.graph = graph;
        this.nodeCount = graph.getNumOfNodes();
        this.expectedEdgeModCound = graph.getEdgeModCount();
        this.minInitID = 0;
        this.predTable = new int[nodeCount];

        Arrays.fill(predTable, UNVISITED);
    }


    /**
     * {@inheritDoc}
     */
    @Override
    public boolean hasNext()
    {
        return !queue.isEmpty() || minInitID < nodeCount;
    }

    /**
     * Checks if the {@link Iterator} should ignore nodes with the specified
     * ids. This method is also used to determine visited nodes. 
     * @param nodeId the id of the node that gets visited
     * @param currId the id of the current node
     * @return {@code true} if the node with {@see nodeId} was visited or should be ignored
     * by the specification of some extended {@see BFSIterator}, {@code false} otherwise.
     * otherwise.
     */
    protected boolean ignore(Edge<N, E> edge)
    {
        return predTable[edge.end.id] != UNVISITED;
    }


    private void updateMinInitID()
    {
        while ( minInitID < nodeCount )
        {
            if ( predTable[minInitID] == UNVISITED )
                break;
            minInitID++;
        }
    }


    /**
     * {@inheritDoc} Gets the next {@link Node} in BFS traversion order.
     */
    public Node<N, E> next()
    {
        if ( expectedEdgeModCound != graph.getEdgeModCount() )
            throw new ConcurrentModificationException();
        if ( queue.isEmpty() )
            if ( minInitID < nodeCount )
            {
                queue.add(graph.nodes[minInitID]);
                predTable[minInitID] = NO_PREDESSOR;
                updateMinInitID();
            }
            else
                throw new NoSuchElementException();

        Node<N, E> curr = queue.pollLast();
        int currId = curr.id;
        for ( Edge<N, E> edge : curr.getOutEdges() )
        {
            if ( !ignore(edge) )
            {
                Node<N, E> node = edge.end;
                int nodeId = node.id;
                queue.addFirst(node);
                predTable[nodeId] = curr.id;
                if ( nodeId == minInitID )
                    updateMinInitID();
            }
        }
        return curr;
    }


    /**
     * Is not supported.
     */
    @Override
    public void remove()
    {
        throw new UnsupportedOperationException("Remove is not supported.");
    }


    /**
     * Gets the predessesor of a special node.
     *
     * @param node
     * @return
     * @throws IllegalStateException if the node was not visited in the traversion process.
     */
    public Node<N, E> getPredessesor(Node<N, E> node)
    {
        return getPredessesor(node.id());
    }


    /**
     * Gets the predessesor of a special node represented by its id.
     *
     * @param nodeId the id of the node.
     * @return
     * @throws IllegalStateException if the node was not visited in the traversion process.
     */
    public Node<N, E> getPredessesor(int nodeId)
    {
        try
        {
            int predId = predTable[nodeId];
            switch (predId)
            {
                case UNVISITED:
                    throw new IllegalStateException("Unvisited node");
                case NO_PREDESSOR:
                    return null;
                default:
                    return graph.getNode(predId);
            }
        }
        catch (ArrayIndexOutOfBoundsException ex)
        {
            throw new IllegalStateException("The node was not added at instantiation.");
        }
    }
}